题解 P2749 【[USACO5.1]夜空繁星Starry Night】

发表于 | 更新于

题意:夜空可以表示为一份天体图，它是一个由字符$0$和$1$组成的二维矩阵，字符$1$表示所在的位置有一颗星；字符$0$表示该位置上是空的.给定一份天体图，用同一个小写英文标识相似的所有星座。相似的星座必须用相同的字母标识，不同的星座表示为不同的字母。标识一个星座，就是将其中各星体对应的字符1替换为相应的小写字母.

难点在于判断图像是否相似，我们采用将每个点之间互相连起来，计算每个点与点之间的距离之和（也可用$hash$、直接写对称旋转函数或八个循环判断），共$\frac{n*(n-1)}{2}$条线段，这种做法的正确性不难证明，当和相同时，每条边长度相等（正确性下面再证），可以将图像看成一个多边形，连接点可以看成将多边形分成许多三角形，根据三角形全等判定条件（$sss$），可以判定每个三角形全等，根据三角形全等推出对应边相等、对应角相等，可证多边形全等
当和相等，每条边也相等的证明：三角形将每个格点的边长设为$1$，故每条线段的长度都为整数或一个整数的开方，整数的小数部分为$0$，整数的开根小数部分取值十分有限，使用$long double$可以将出错率大大降低。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
int k,tail,tx[200000],ty[200000],n,m,a[300000],b[300000],dx[]={-1,-1,-1,0,0,1,1,1},dy[]={-1,0,1,-1,1,-1,0,1};
char s[3000][3000],p='a',u[3999];
long double t[39];
void dfs(int x,int y,char q,char p){//深搜求联通块（广搜也可）
    for (int i=0;i<8;i++){//根据题意是八个方向
        int xx=x+dx[i],yy=y+dy[i];
        if (xx<1||xx>n||yy<0||yy>=m||s[xx][yy]!=p) continue;
        tx[++tail]=xx;ty[tail]=yy;
        s[xx][yy]=q;
        dfs(xx,yy,q,p);
    }
}
void check(int x,int y){
    long double res=0;
    for (int i=1;i<=tail;i++)
        for (int j=1;j<=tail;j++)
            res+=sqrt((tx[i]-tx[j])*(tx[i]-tx[j])+(ty[i]-ty[j])*(ty[i]-ty[j]));//计算每个点与点之间的直线距离和
    for (int i=1;i<=k;i++)
        if (abs(res-t[i])<0.00001){//浮点数的判定相等的方法
            p--;char o=s[x][y];
            s[x][y]=u[i];
            dfs(x,y,u[i],o);//若与前面重复则重新赋值
            return;
        }
    t[++k]=res;u[k]=p;//不重复则加入数组（也可用map）
}
int main() {
//    freopen("star.in", "r", stdin), freopen("star.out", "w", stdout);
    cin>>m>>n;
    for (int i=1;i<=n;i++)
        scanf("%s",s[i]);
    for (int i=1;i<=n;i++)
        for (int j=0;j<m;j++)
            if (s[i][j]=='1'){
                s[i][j]=p;
                tx[1]=i;ty[1]=j;
                tail=1;
                dfs(i,j,p,'1');
                check(i,j);
                p++;
            }
    for (int i=1;i<=n;i++){
        for (int j=0;j<m;j++) 
            cout<<s[i][j];
        cout<<endl;
    }
}